A virtual machine is software that acts as an interface between compiler code and a hardware platform. Once a virtual machine has been provided for a platform, any compatible program can run on that platform without necessitating hardware-specific alterations. When running a virtual machine, one or more classes and interfaces may be loaded. A class is a template definition of the methods and variables in a particular kind of object. An interface is a reference type whose members are constants and abstract methods.
Some of the program commands in a virtual machine, also called bytecodes, need to check whether the class of a particular instance is a subclass of another class, or implements a particular interface. In the Java™ Virtual Machine created by Sun Microsystems, Inc. of Palo Alto, Calif., these bytecodes are aastore, checkcast, and instance of.
The hierarchy of classes in a virtual machine may be thought of as a tree structure. Therefore, one way to implement this checking is to begin at the node representing the class being checked, and walk up the hierarchy until the possible superclass or interface is found or the root of the class hierarchy is reached.
This approach, however, can be slow in many cases. There are presently two optimization techniques that may be used to speed up this approach, but as will be seen they each suffer their own drawbacks. The first technique, known as subtype caching, is to put the subclass into a cache for the superclass' subtype when a superclass of the subclass is found. While this speeds up the search when a matching superclass is found, caching does not occur when the subtype check fails. Additionally, when a class or interface is tested against more than two subclasses (the currently implemented cache size), the cache will constantly be trashed.
The second technique, known as subtype matrix generation, involves creating a matrix that stores information regarding the relationships between the classes. While this approach is fast, it requires n2 space for the matrix, where n is the number of classes in the system. This results in wasted memory space. Additionally, classes and interfaces need to know their index for the matrix lookup.
What is needed is a technique that allows for fast subtype checking in an efficient manner.